home *** CD-ROM | disk | FTP | other *** search
/ Developer CD Series 1992 June: ROMin Holiday / ADC Developer CD (1992-06) (''ROMin Holiday'')_iso / Developer Connection - 06-1992.iso / Development Platforms / Apple II / Essentials / Technical.Notes / Pasc / TN.PASC.014 < prev    next >
Encoding:
Text File  |  1988-12-21  |  8.0 KB  |  202 lines  |  [TEXT/pdos]
  1. Apple II
  2. Technical Notes
  3. _____________________________________________________________________________
  4.                                                   Developer Technical Support
  5.  
  6.  
  7. Pascal
  8. #14:    Apple Pascal 1.3 TREESEARCH and IDSEARCH
  9.  
  10. Revised by:    Cheryl Ewy                                       November 1988
  11. Written by:    Cheryl Ewy                                           June 1985
  12.  
  13. This Technical Note describes the TREESEARCH and IDSEARCH routines which were 
  14. built into Pascal 1.2 and earlier, but which are separate entities for Pascal 
  15. 1.3.
  16. _____________________________________________________________________________
  17.  
  18.  
  19. Introduction
  20.  
  21. In Apple II Pascal versions 1.0 through 1.2, TREESEARCH and IDSEARCH were 
  22. special-purpose built-in routines which could be called from within a Pascal 
  23. program.  The routines existed primarily for use by the Compiler and Libmap 
  24. but were also available for use by applications.  In Apple II Pascal 1.3, the 
  25. routines were removed due to space requirements.  Since some applications use 
  26. these routines, they are being supplied as 6502 codefiles which can be linked 
  27. to Pascal programs.  To use the routines, the Pascal host program must declare 
  28. them as EXTERNAL (see the following sections for details).  After compiling 
  29. the host program, use the Linker to link the file TRS.CODE (TREESEARCH) or the 
  30. file IDS.CODE (IDSEARCH).
  31.  
  32.  
  33. The TREESEARCH Function
  34.  
  35. TREESEARCH is a fast assembly language function for searching a binary tree 
  36. with a particular kind of structure.  The external declaration is:
  37.  
  38.     FUNCTION TREESEARCH (ROOTPTR : ^NODE;
  39.                         VAR NODEPTR : ^NODE;
  40.                         NAMEID : PACKED ARRAY [1..8] OF CHAR) :INTEGER;
  41.         EXTERNAL;
  42.  
  43. The call syntax is:
  44.  
  45.     RESULT := TREESEARCH (ROOTPTR, NODEPTR, NAMEID);
  46.  
  47. where ROOTPTR is a pointer to the root node of the tree to be searched, 
  48. NODEPTR is a reference to a pointer variable to be updated by TREESEARCH, and 
  49. NAMEID contains the eight-character name to be searched for in the tree.
  50.  
  51. The nodes in the binary tree are assumed to be linked records of the type:
  52.  
  53. NODE = RECORD
  54.               NAME : PACKED ARRAY[1..8] OF CHAR;
  55.               LEFTLINK, RIGHTLINK : ^NODE;
  56.  
  57.               {other fields can be anything}
  58.  
  59.        END; 
  60.  
  61. The actual names of the type and the field identifiers are not important; 
  62. TREESEARCH assumes only that the first eight bytes of the record contain an 
  63. eight-character name and are followed by two pointers to other nodes.
  64.  
  65. It is also assumed that names are not duplicated within the tree and are 
  66. assigned to nodes according to an alphabetical rule; for a given node, the 
  67. name of the left subnode is alphabetically less than the name of the node, and 
  68. the name of the right subnode is alphabetically greater than the name of the 
  69. node.  Finally, any links that do not point to other nodes should be NIL.
  70.  
  71. TREESEARCH can return any of three values:
  72.  
  73.      0    The name passed to TREESEARCH (as the third parameter) has been 
  74.           found in the tree.  The node pointer (second parameter) now points 
  75.           to the node with the specified name.
  76.      1    The name is not in the tree.  If it is added to the tree, it 
  77.           should be the right subnode of the node pointed to by the node 
  78.           pointer.
  79.     -1    The name is not in the tree.  If it is added to the tree, it 
  80.           should be the left subnode of the node pointed to by the node 
  81.           pointer.
  82.  
  83. The TREESEARCH function does not perform any type checking on the parameters 
  84. passed to it.
  85.  
  86.  
  87. The IDSEARCH Procedure
  88.  
  89. IDSEARCH is a fast assembly language procedure that scans Apple II Pascal 
  90. source text for identifiers and reserved words.  Note that IDSEARCH recognizes 
  91. only identifiers and reserved words--you have to scan for special characters 
  92. and comments yourself.
  93.  
  94. The external declaration is:
  95.  
  96.     PROCEDURE IDSEARCH (VAR OFFSET:INTEGER;
  97.                        VARBUFFER:BYTESTREAM);
  98.         EXTERNAL;
  99.  
  100. The call syntax is:
  101.  
  102.     IDSEARCH (OFFSET, BUFFER);
  103.  
  104. To use IDSEARCH, you must include the following declarations in your program.  
  105. Note that the variables (except BUFFER) must be declared in exactly the order 
  106. and types shown.
  107.  
  108. TYPE 
  109.  
  110.     {SYMBOL is the enumerated type of symbols in the Apple // Pascal 
  111. language}
  112.  
  113.     SYMBOL =    (IDENT,COMMA,COLON,SEMICOLON,LPARENT,RPARENT,DOSY,TOSY,
  114.                 DOWNTOSY,ENDSY,UNTILSY,OFSY,THENSY,ELSESY,BECOMES,LBRACK,
  115.                 RBRACK,ARROW,PERIOD,BEGINSY,IFSY,CASESY,REPEATSY,WHILESY,
  116.                 FORSY,WITHSY,GOTOSY,LABELSY,CONSTSY,TYPESY,VARSY,PROCSY,
  117.                 FUNCSY,PROGSY,FORWARDSY,INTCONST,REALCONST,STRINGCONST,
  118.                 NOTSY,MULOP,ADDOP,RELOP,SETSY,PACKEDSY,ARRAYSY,RECORDSY,
  119.                 FILESY,OTHERSY,LONGCONST,USESSY,UNITSY,INTERSY,IMPLESY,
  120.                 EXTERNLSY,OTHERWSY); 
  121.  
  122.     {The reserved words corresponding to the above symbols are as follows - 
  123.  
  124.     DOSY       - DO       WITHSY      - WITH        RELOP      - IN
  125.     TOSY       - TO       GOTOSY      - GOTO        SETSY      - SET
  126.     DOWNTOSY   - DOWNTO   LABELSY     - LABEL       PACKEDSY   - PACKED 
  127.     ENDSY      - END      CONSTSY     - CONST       ARRAYSY    - ARRAY 
  128.     UNTILSY    - UNTIL    TYPESY      - TYPE        RECORDSY   - RCORD
  129.     OFSY       - OF       VARSY       - VAR         FILESY     - FILE
  130.     THENSY     - THEN     PROCSY      - PROCEDURE   USESSY     - USES
  131.     ELSESY     - ELSE     FUNCSY      - FUNCTION    UNITSY     - UNIT 
  132.     BEGINSY    - BEGIN    PROGSY      - PROGRAM     INTERSY    -.INTERFACE
  133.     IFSY       - IF                     SEGMENT     IMPLESY    -.IMPLEMENTATION
  134.     CASESY     - CASE     FORWARDSY   - FORWARD     EXTERNLSY  - EXTERNAL
  135.     REPEATSY   - REPEAT   NOTSY       - NOT         OTHERWSY   - OTHERWISE
  136.     WHILESY    - WHILE    MULOP       - AND,DIV,MOD
  137.     FORSY      - FOR      ADDOP       - OR          } 
  138.  
  139.     {OPERATOR expands the multiplicative (MULOP), additive (ADDOP) and
  140.     relational (RELOP) operators}
  141.  
  142.     OPERATOR =     (MUL,RDIV,ANDOP,IDIV,IMOD,PLUS,MINUS,OROP,LTOP,LEOP,
  143.                    GEOP,GTOP,NEOP,EQOP,INOP,NOOP); 
  144.  
  145.     ALPHA = PACKED ARRAY [1..8] OF CHAR; 
  146.  
  147. VAR 
  148.     {the next four variables must be declared in the order shown}
  149.     OFFSET : INTEGER;
  150.     SY : SYMBOL; 
  151.     OP : OPERATOR;
  152.     ID : ALPHA;
  153.  
  154. IDSEARCH begins by looking for an identifier at the character pointed to by 
  155. BUFFER[OFFSET] and assumes that this character is alphabetic.  IDSEARCH 
  156. produces the following results:
  157.  
  158. o    BUFFER[OFFSET] points to the character following the identifier 
  159.      just found.
  160. o    ID contains the first eight alphanumeric characters of the 
  161.      identifier just found, left justified and padded with spaces as 
  162.      necessary.
  163. o    SY contains the symbol associated with the identifier just found 
  164.      if the identifier is a reserved word or IDENT if the identifier is 
  165.      not a reserved word.  For example, the identifier MOD translates 
  166.      to MULOP; the identifier ARRAY translates to ARRAYSY, and the 
  167.      identifier MYLABEL translates to IDENT.
  168. o    OP contains the operator value which corresponds to the identifier 
  169.      just found if the identifier is an operator, or NOOP if the 
  170.      identifier is not an operator.  For example, the identifier MOD 
  171.      translates to IMOD, the identifier ARRAY translates to NOOP, and 
  172.      the identifier MYLABEL translates to NOOP.
  173.  
  174. The following is an example of calling IDSEARCH:
  175.  
  176.     BEGIN
  177.         IF BUFFER[OFFSET] IN ['A'..'Z','a'..'z'] THEN
  178.             IDSEARCH (OFFSET, BUFFER);     
  179.     END;
  180.  
  181. The following is an algorithmic representation of IDSEARCH:
  182.  
  183.     PROCEDURE IDSEARCH (VAR OFFSET:INTEGER; VAR BUFFER:BYTESTREAM);
  184.     BEGIN 
  185.         ID := ScanIdentifier (OFFSET, BUFFER);
  186.         SY := LookUpReservedWord (ID); 
  187.         OP := LookUpOperator (ID);
  188.     END;
  189.  
  190. ScanIdentifier increments OFFSET until BUFFER[OFFSET] is no longer part of an 
  191. identifier, copying the first eight alphanumeric characters passed into ID 
  192. (left justified, padding with spaces).
  193.  
  194. LookUpReservedWord translates an identifier into the associated symbol 
  195. (defaulting to IDENT).
  196.  
  197. LookUpOperator translates an identifier into the associated operator 
  198. (defaulting to NOOP).
  199.  
  200.  
  201.  
  202.